1. Field of the Invention
The invention relates to method and apparatus for simulating systems that are configured in the form of networks of arranged processing elements. For example, the invention may be used to assist in the design of a digital logic network comprising a plurality of digital logic circuits, and determine the output signals that would be developed by the network in response to the digital input signals. The simulation apparatus constructed in accordance with the invention may thus be used to verify the logical operations performed by the network before the network is actually constructed.
The invention also finds wide utility in a number of other fields in which systems can be analyzed in the form of trees or networks, including the design and verification of processing networks, pipe and electric and telephone wire networks, road networks and floor plans. Furthermore, the invention will find utility in such fields as image processing and image analysis, in which an image can be divided into a number of picture elements, or "pixels", and the pixels analyzed in relation to their neighbors. The invention will further find utility in the design and verification of non-digital electronic circuits.
2. Description of the Prior Art
In the past, the logical operation of electronic networks has been verified by constructing a prototype of the network on a "breadboard", and connecting appropriate test equipment. An input signal is then applied to the inputs of the network, the output signal generated by the network is sensed, and the actual output signal is compared to the desired output signal to determine if they are identical. The process of applying the input signal and sensing the output signal must be repeated for every possible input signal to completely verify the circuit design. For some circuitry, for example a three-to-eight digital decoder, in which one of eight output lines is energized in response to a selected encoding of the three input lines, only eight different sets of three input signals are required to test the circuit. However, for a sixteen-bit adder, which generates sum and carry signals in response to two sixteen-bit input words, in excess of one hundred thousand possible combinations of the input signals are possible. It is apparent that verification of a breadboard prototype of such a circuit by this method is an extremely lengthy process, if it were desired to test the circuit with all possible combinations of input signals.
The process of verifying the design of other networks can also be a lengthy task. Piping, wire for electrical power and telephone networks, roadways and floor plans normally cannot be breadboarded, and therefore the design must be verified from the plans and testing in the field. This can be expensive if a design error must be corrected.
Furthermore, image processing and analysis, including enhancement of faint images and recognition of various shapes, can be a lengthy process if done manually. A number of computer algorithms have been written to attempt to automate the process of image recognition, but to date these have been fairly slow.
Copending application no. 698,474, assigned to the assignee of the present inventions, discloses a simulator that simulates a network of an array of processing elements by determining the output signals that would be present at the output terminals in response to a set of input signals provided by an operator at the input terminals. The network is formed from a predetermined set of processing elements, each element in the set having predetermined input and output terminals and performing a predefined logical operation on input signals present at the input terminals, the output signals at the output terminals of each element being determined by the input signals and the logical operation defined therefor.
In the aforementioned simulator, each type of processing element is represented by a code representation that is stored in a symbol memory. The symbol memory includes a plurality of storage locations having row and column addresses which correspond to the rows and columns of the network array. Each storage location stores the representations of the processing element at the corresponding location in the network array. The simulator also includes a data memory which also includes storage locations having row and column addresses which correspond to the rows and columns in the network array, and a separate register. The simulator simulates the network in a series of iterations. During each iteration, the simulator determines the type of processing element that is present in a location in the array and retrieves input data representative of the input signals which would be present in the network, which data is obtained from the data memory and register. The simulator then determines the output signals which would be generated by the processing element and stores data representative of the output signals in the data memory and register.
The simulator described in the aforementioned application processes the processing elements in each row, from left to right, and from the top row to the bottom in the array. Thus, the network is constrained to have its input terminals at the left and upper portions of the array, and the outputs to the right and lower portions. In such a system, the processing elements must have inputs from the left and above and outputs to the right and down. Furthermore, since the simulator steps through all of the rows and columns in the array, it will process some locations at which no network elements are located, which wastes time in the simulator.